Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public boolean isBalanced(TreeNode root) {
  12.     return getHeight(root) >= 0;
  13.   }
  15.   int getHeight(TreeNode root) {
  16.     if (root == null)
  17.       return 0;
  19.     int left = getHeight(root.left);
  21.     if (left < 0)
  22.       return -1;
  24.     int right = getHeight(root.right);
  26.     if (right < 0)
  27.       return -1;
  29.     if (Math.abs(left - right) > 1)
  30.       return -1;
  32.     return 1 + Math.max(left, right);
  33.   }
  34. }